package com.mlh.dp.old;

// 题目：给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
// 举例：
// 输入: s1 = "sea", s2 = "eat"
// 输出: 231
// 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
// 在 "eat" 中删除 "t" 并将 116 加入总和。
// 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。


public class MinimumDeleteSum {

    public static void main(String[] args) {
        String s1="sea";
        String s2="eat";
        System.out.println(method1(s1,s2));
    }


    //这一题是自己写出来的，因为也是涉及到2个字符串的问题
    //想了一下 用 最小编辑距离的方法来解  只需要稍作修改就可以
    public static int method1(String s1,String s2){
        char[]sc1=s1.toCharArray();
        char[]sc2=s2.toCharArray();
        int sc1Len=sc1.length;
        int sc2Len=sc2.length;
        int [][]dp =new int[sc1Len+1][sc2Len+1];


        dp[0][0]=0;
        for(int i=1;i<=sc1Len;i++){
            for(int j=0;j<i;j++){
                dp[i][0]+=(int)sc1[j];
            }
        }

        for(int i=1;i<=sc2Len;i++){
            for(int j=0;j<i;j++){
                dp[0][i]+=(int)sc2[j];
            }
        }

        for(int i=1;i<=sc1Len;i++){
            for(int j=1;j<=sc2Len;j++){
                if(sc1[i-1]==sc2[j-1]){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j]+(int)sc1[i-1],dp[i][j-1]+(int)sc2[j-1]),dp[i-1][j-1]);
                }else {
                    dp[i][j]=Math.min(Math.min(dp[i-1][j]+(int)sc1[i-1],dp[i][j-1]+(int)sc2[j-1]),dp[i-1][j-1]+(int)sc1[i-1]+(int)sc2[j-1]);
                }
            }
        }

        for(int i=0;i<=sc1Len;i++){
            for(int j=0;j<=sc2Len;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }

        return dp[sc1Len][sc2Len];
    }
}
